<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
  //封装双向链表
  function DoublyLinkedList() {
  //  内部类：节点类
    function Node(data){
      this.data = data
      this.prev = null
      this.next = next
    }

    //属性
    this.head = null
    this.tail = null
    this.length = 0

  //  常见方法的封装
  //  1、append方法（先尾部添加一个新的项）
    DoublyLinkedList.prototype.append = function(data){
    //  1、根据data创建节点
      var newNode = new Node(data)

    //  2、判断添加的是否是第一个节点
      if(this.length == 0){
        this.head = newNode
        this.tail = newNode
      }else{ //不是第一个节点
        newNode.prev = this.tail
        this.tail.next = newNode
        this.tail = newNode
      }

    //  3、链表长度+1
      this.length += 1
    }

  //  2、将链表转成字符串形式
  //  2.1、toString方法
    DoublyLinkedList.prototype.toString = function(){
      return this.backwardString()
    }

  //  2.2、forwardString方法（返回正向遍历的节点字符串）
    DoublyLinkedList.prototype.forwardString = function(){
    //  1、定义变量
      var current = this.tail
      var resultString = ""

    //  2、依次向前遍历，获取每一个节点
      while(current){
        resultString += current.data + " "
          current = current.prev
      }
      return resultString
    }

  //  2.3、backwardString方法（返回反向遍历的节点字符串）
    DoublyLinkedList.prototype.backwardString = function(){
        //  1、定义变量
        var current = this.head
        var resultString = ""

        //  2、依次向后遍历，获取每一个节点
        while(current){
            resultString += current.data + " "
            current = current.next
        }
        return resultString
    }

  //  3、insert方法
      DoublyLinkedList.prototype.insert = function(position,data){
      //  1、越界判断
          if(position < 0 || position > this.length) return false

      //  2、根据data创建新的节点
          var newNode = new Node(data)

      //  3、判断原来的列表是否为空
          if(this.length == 0){ //链表是空的
              //head指针和tail指针都指向新的节点
              this.head = newNode
              this.tail = newNode
          }else{
              if(position == 0){ // 3.1、当插入到第一位
                  this.head.prev = newNode //原来第一位的节点的prev指向新插入的节点
                  newNode.next = this.head //新插入节点的next指向原来的第一个节点
                  this.head = newNode //head指针指向新插入的节点
              }else if(position == this.length){//3.2、当插入到最后一位
                  newNode.prev = this.tail //新插入节点的prev指向原来的最后一个节点
                  this.tail.next = newNode //原来最后一个节点的next指向新插入的节点
                  this.tail = newNode //tail指针指向新插入的节点
              }else{ //3.3、插入到中间任意位置
                  var current = this.head
                  var index = 0

                  //找到要插入的位置，使current指向该位置节点
                  while(index++ < position){
                      current = current.next
                  }

              //    修改指针
                  newNode.next = current //新插入节点的next指向原本该位置的节点
                  newNode.prev = current.prev //新插入节点的prev指向原本该位置节点的上一个节点
                  current.prev.next = newNode //该位置节点的上一个节点的next指向新插入的节点
                  current.prev = newNode //该位置节点的prev指向新插入的节点
              }
          }

      //    4、链表长度+1
          this.length += 1
      }

  //    4、get方法
      DoublyLinkedList.prototype.get = function(position){
      //1、越界判断
          if(position < 0 || position >= this.length) return null

      //    this.length / 2 > position: 从头向后遍历
      //    this.length / 2 < position: 从后向前遍历

      //2、获取元素
          var index = 0
          if((this.length / 2) > position){
              var current = this.head
              while(index++ < position){
                  current = current.next
              }
          }else{
              var current = this.tail
              while(index++ < (this.length - position)){
                  current = current.prev
              }
          }
          return current.data
      }

  //    5、indexOf方法
      DoublyLinkedList.prototype.indexOf = function(data){
      //  1、定义变量
          var current = this.head
          var index = 0

      //  2、查找data相同的节点
          while(current){
              if(current.data == data){
                  return index
              }
              current = current.next
              index += 1
          }

          return -1 //没有找到则返回-1
      }

  //    6、update方法
      DoublyLinkedList.prototype.update = function(position,newData){
      //  1、越界判断
          if(position < 0 || position >= this.length)return false

      //  2、寻找正确的节点
          var current = this.head
          var index = 0
          while(index++ < position){
              current = current.next
          }

      //  3、修改找到的节点的data信息
          current.data = newData

          return true
      }

  //    7、removeAt方法
      DoublyLinkedList.prototype.removeAt = function(position){
      //  1、越界判断
          if(position < 0 || position >= this.length)return null

      //  2、判断是否只有一个节点
          var current = this.head
          if(this.length == 1){ //链中只有一个节点
              this.head = null
              this.tail = null
          }else{
              if(position == 0){//删除的是第一个节点
                  this.head.next.prev = null
                  this.head = this.head.next
              }else if(position == this.length -1){//删除的是最后一个节点
                  current = this.tail
                  this.tail.prev.next = null
                  this.tail = this.tail.prev
              }else{ //删除的是中间的节点
                  var index = 0

                  while(index++ < position){
                      current = current.next
                  }

                  current.prev.next = current.next
                  current.next.prev = current.prev
              }
          }

      //  3、长度-1
          this.length -= 1

          return current.data
      }

  //    8、remove方法
      DoublyLinkedList.prototype.remove = function(data){
      //  1、根据data获取下标值
          var index = this.indexOf(data)

      //  2、根据index删除对应位置的节点
          return this.removeAt(index)
      }

  //    9、isEmpty方法
      DoublyLinkedList.prototype.isEmpty = function(){
        return this.length == 0
      }

  //    10、size方法
      DoublyLinkedList.prototype.size = function(){
        return this.length
      }

  //    11、获取链表的第一个元素
      DoublyLinkedList.prototype.getHead = function(){
        return this.head.data
      }

  //    12、获取链表的第一个元素
      DoublyLinkedList.prototype.getTags = function(){
        return this.tail.data
      }

  }
</script>
</body>
</html>